Теорема Кантора о булеане

Для любого множества $A$ выполнено неравенство: $|A| < |2^A|$.

Пусть $f(a) = \{a\}$ для всех $a \in A$. $f$ — инъекция из $A$ в $2^A$; значит, $|A| \leq |2^A|$. В обратную сторону докажем от противного: Пусть $\phi\mathpunct{:}~~ 2^A \to A$ — инъекция. Для каждого подмножества $B \subset A$: * назовем элемент $\phi(B)$ синим, если $\phi(B) \in B$ * назовем элемент $\phi(B)$ красным, если $\phi(B) \notin B$ $\Rightarrow$ так как $\phi$ — инъекция, любой элемент $A$ покрашен не более чем в один цвет. Рассмотрим множество $R$, состоящее из всех красных элементов $A$. * если $\phi(R) \in R$, то элемент $\phi(R)$ по определению синий $\iff \phi(R) \notin R$ * если $\phi(R) \notin R$, то элемент $\phi(R)$ по определению красный $\iff \phi(R) \in R$ $\Rightarrow$ противоречие; значит, $\phi$ не существует и $|2^A| \not\leq |A|$. $\square$